#ifndef _RANDOMIZER_HH_
#define _RANDOMIZER_HH_
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
#include "Bug.h"



template<typename _ObjectIterator, typename _Weight>
inline _ObjectIterator randomized_selection(_ObjectIterator begin, _ObjectIterator end, _Weight get_weight)
{
#ifdef DEBUG
  static bool message_sent = false;
#endif
  
  // accumulate probabilities for selected actions
  std::vector<double> cum_weights;
  double sum = 0;
  for(_ObjectIterator it = begin; it!=end; ++it)
    {
      sum += get_weight(*it);
      cum_weights.push_back(sum);
    }

  // at last one option should have non-zero weight!
  if(fabs(sum)<=std::numeric_limits<double>::epsilon())
    {
#ifdef DEBUG
      if(not message_sent)
	bug << "WARNING: at last one option should have non-zero weight!"
	    << std::endl;
      message_sent = true;
#endif
      return begin + rand() % (end - begin);
    }
  

  double rval = static_cast<double>(rand()*sum)/RAND_MAX;
  
  // at last one action should have strictly positive weight
  std::vector<double>::const_iterator i = std::upper_bound(cum_weights.begin(), cum_weights.end(), rval);
  if(rand()%1000==0 or i == cum_weights.end())
    {
      ASSERT(i != cum_weights.end());
      for(std::vector<double>::const_iterator it=cum_weights.begin();
	  it != cum_weights.end(); ++it)
	{
	  bug << ' ' << get_weight(*it);
	}
      bug << std::endl;
    }
  
  
  return begin + (i - cum_weights.begin());
}


double identity(double val);



std::vector<double>::iterator 
inline randomized_selection(std::vector<double>::iterator begin, std::vector<double>::iterator end)
{
  return randomized_selection(begin, end, identity);
}


  
  
#endif /* _RANDOMIZER_HH_ */
